// 1.大数相加
const bigAdd = (a, b) => {
    let maxLen = Math.max(a.length, b.length);
    a = a.padStart(maxLen, 0);
    b = b.padStart(maxLen, 0);

    let curry = 0;
    let cur = 0;
    let sum = "";

    for(let i = maxLen -1; i > 0; i--){
        cur = a[i] + b[i] + curry;
        curry = Math.floor(cur / 10);
        sum = cur % 10 + sum;
    }

    if(curry === 1)
        sum = '1' + sum;

    return sum;
}

// 2.带并发限制的fetch
const sendRequest = (urls, max, callback) => {
    let pending_count = 0;
    let idx = 0;
    while(pending_count <= max)
        _fetch(urls[idx++]);

    async function _fetch(url){
        if(!url) return
        pending_count++;
        await fetch(url)
        pending_count--;
        _fetch(urls[idx++]);
        pending_count || callback && callback();
    }   
}

let fetch = function(idx){
    return new Promise((resolve)=>{
        let timeout = parseInt(Math.random() * 1e4);
        setTimeout(() => {
            resolve(idx);
        }, timeout)
    })
}

// 二分查找
function binary_search(low, high, key, arr){
    if(low > high) return -1;
    let mid = parseInt((low + high) / 2);
    if(arr[mid] === key)
        return mid;
    else if(arr[mid] > key){
        high = mid -1;
        return binary_search(low, high, key, arr);
    }else if(arr[mid] < key){
        low = mid + 1;
        return binary_search(low, high, key, arr);
    }
}

// 发布订阅模式
function Subject(){
    this.observers = [];
}

Subject.prototype = {
    subscribe: function(observer, option){
        let {once = false, priority = 0} = option;
        this.observers.push(observer, once, priority);
        this.observers.sort((a, b) => b.priority - a.priority);
    },
     
    unsubscribe: function(observerToRemove){
        this.observers = this.observers.filter(observer =>
            observer !== observerToRemove
        )
    },

    publish: function(data){
        let current = [...this.observers];
        current.forEach(observer => {
            Promise.resolve().then(() =>
                observer.observer(data)
            )
            if(observer.once)
                current.unsubscribe(observer);
        })
    }
}

const subject = new Subject();
function onlyOnce(data){
    console.log('只执行一次', data);
}
subject.subscribe(onlyOnce,{once: true});
subject.publish('一次');

// 反转列表
const reverseList = (head) => {
    let prev = null;
    let cur = head;
    let next = head;
    while(cur){
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

function ListNode(val, next = null){
    this.val = val;
    this.next = next;
}


// 防抖:事件在N秒后执行回调，如果在N秒内又被触发，会重新计时。
function debounce(fn, wait){
    let timer = null;
    return function(...args){
        if(timer)
            clearTimeout(timer);
        else{
            timer = setTimeout(() => {
                fn.apply(this, args);
                timer = null;
            }, wait)
        }
    }
}

// 节流: 事件在触发N秒后执行回调，N秒内触发无效
function throttle(fn, wait){
    let timer = null;
    return function(...args){
        if(!timer)
            timer = setTimeout(() => {
                fn.apply(this, args);
                timer = null;
            }, wait);
    }
}

function throttle1(fn, wait) {
    let prev = Date.now();
    return function(...args){
        let now = Date.now();
        if(now - prev >= wait){
            fn.apply(this, args);
            prev = Date.now();
        }
    }
}

// 归并排序
function merge(left, right){
    const result = [];
    let i = 0, j = 0;
    while(i < left.length && j < right.length){
        if(left[i] <= right[i])
            result.push(left[i]);
        else
            result.push(right[i]);
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr){
    if(arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

// 函数柯利化
function curry(fn, ...args){
    return fn.length === args.length ? fn(...args):
    curry.bind(null, fn, ...args);
}

    // 动态传入参数个数
    function dynamicCurry(fn){
        const args = [];
        function curried(...newArgs){
            args.push(...newArgs);
            return curried;
        }

        curried.end = function(){
            return fn(...args);
        }
        return curried;
    }


// 将数组转为树形结构
var menu_list = [{
    id: '1',
    menu_name: '设置',
    menu_url: 'setting',
    parent_id: 0
   }, {
    id: '1-1',
    menu_name: '权限设置',
    menu_url: 'setting.permission',
    parent_id: '1'
   }, {
    id: '1-1-1',
    menu_name: '用户管理列表',
    menu_url: 'setting.permission.user_list',
    parent_id: '1-1'
   }, {
    id: '1-1-2',
    menu_name: '用户管理新增',
    menu_url: 'setting.permission.user_add',
    parent_id: '1-1'
   }, {
    id: '1-1-3',
    menu_name: '角色管理列表',
    menu_url: 'setting.permission.role_list',
    parent_id: '1-1'
   }, {
    id: '1-2',
    menu_name: '菜单设置',
    menu_url: 'setting.menu',
    parent_id: '1'
   }, {
    id: '1-2-1',
    menu_name: '菜单列表',
    menu_url: 'setting.menu.menu_list',
    parent_id: '1-2'
   }, {
    id: '1-2-2',
    menu_name: '菜单添加',
    menu_url: 'setting.menu.menu_add',
    parent_id: '1-2'
   }, {
    id: '2',
    menu_name: '订单',
    menu_url: 'order',
    parent_id: 0
   }, {
    id: '2-1',
    menu_name: '报单审核',
    menu_url: 'order.orderreview',
    parent_id: '2'
   }, {
    id: '2-2',
    menu_name: '退款管理',
    menu_url: 'order.refundmanagement',
    parent_id: '2'
   }
]

const buildTree = (arr) => {
    const result = {};
    const temp = {};
    for(let i = 0; i < arr.length; i++)
        temp[arr[i].id] = arr[i];

    for(let i in temp) {
        if(temp[i].parent_id){
            if(!temp[temp[i].parent_id].children)
                temp[temp[i].parent_id].children = new Object();
            temp[temp[i].parent_id].children[temp[i].id] = temp[i]
        }else {
            result[temp[i].id] = temp[temp[i].id]; 
        }
    }
    return result;
}

// 将http header转换为JS对象
/**
 * --- 测试用例 ---
 * 
 * 输入：
 * `Accept-Ranges: bytes 
 * Cache-Control: max-age=6000, public
 * Connection: keep-alive
 * Content-Type: application/javascript`
 * 
 * 输出：
 * {
 *   "Accept-Ranges": "bytes",
 *   "Cache-Control": "max-age=6000, public",
 *   Connection: "keep-alive",
 *   "Content-Type": "application/javascript"
 * }
 */
const solution = (s) => {
    const result = {};
    const arr = s.split('\n');
    arr.forEach(item => {
        let temp = item.split(':');
        result[temp[0]] = temp[1];
    })
    return result;
}

// 快速排序
function quickSort(start, end, arr){
    if(start >= end) return;
    let pivot = arr[start];
    let left = start;
    let right = end;

    while(left < right){
        while(left < right && pivot <= arr[right])
            right--;
        arr[left] = arr[right];
        while(left < right && pivot >= arr[left])
            left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(start, left-1, arr);
    quickSort(left+1, end, arr );
    return arr;
}

// 冒泡排序
function bubbleSort(arr){
    for(let i = 0; i < arr.length - 1; i++){
        for(let j =0; j < arr.length - i -1;j++){
            if(arr[j] > arr[j+1])
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        }
    }
    return arr;
}

// 判断是否是回文数
function isPalindrome(s){
    return s.toString().split('').reverse().join('') === s.toString();
}

function isPalindrome2(s) {
    if(s < 0 || (s % 10 === 0 && x != 0))
        return false;
    let reversed = 0;
    while(s > reversed){
        reversed = reversed * 10 + s % 10;
        s = Math.floor(s / 10);
    }
    return s === reversed || x === Math.floor(reversed / 10);
}

// 求出一个集合所有的子集
const subSets = (nums) => {
    const result = [];

    function dfs(index, path){
        result.push(path.slice())
        for(let i = index; i < nums.length; i++) {
            path.push(nums[i]);
            dfs(i+1, path);
            path.pop()
        }
    }
    
    dfs(0, []);
    return result;
}


// 全排列
const permute = (nums) => {
    const result = [];
    const used = {};

    function dfs(path){
        if(path.length === nums.length){
            result.push(path.slice());
            return;
        }

        for (let num of nums){
            if(used[num]) continue;
            path.push(num);
            used[num] = true;
            dfs(path);
            path.pop();
            used[num] = false;
        }
    }

    dfs([]);
    return result;
}

// 深拷贝
function deepCopy(obj) {
    if(typeof obj !== 'object' || obj === null)
        return obj;
    const result = obj instanceof Array ? [] : {};
    for(let i in obj){
        if(obj.hasOwnProperty(i))
            result[i] = deepCopy(obj[i]);
    }
    return result;
}


// 实现千位分隔符
function numFormat(num) {
    num = num.toString().split(".");
    let arr = num[0].split("").reverse();
    const res = [];
    for(let i = 0; i < arr.length; i++){
        if(i !==0 && i%3==0){
            res.push(',');
        }
        res.push(arr[i]);
    }
    res.reverse();
    if(arr[1])
        return res.join('').concat('.' + arr[1]);
    else
        return res.join('');
}

// 实现异步加载图片
function loadImg(url){
    return new Promise((resolve, reject) => {
        const img = new Image();
        img.src = url;

        img.onload = () => {
            resolve(img);
        }

        img.onerror = (err) => {
            reject(err);
        } 
    })
} 

loadImg(url).then(value => 
    document.body.appendChild(value)
).catch(err =>
    console.err(err)
)

// 实现字符串翻转
function reverse(s) {
    return s.length <= 1 ? s :
    reverse(s.slice(1)) + s[0];
}

function reverse1(s){
    let res = "";
    for(let i = s.length-1;i>0;i--){
        res = res + s[i];
    }
    return res;
}

// 实现trim方法
function myTrim(s) {
    let reg = /^\s+|\s+$/g;
    return s.replace(reg,'');
}

// 实现 setTimeout模拟setInterval
function mySetInterval(fn, wait) {
    let res = {target: ''};
    function test() {
        fn();
        res.target = setTimeout(test,wait);
    }
    test();
    return res;
}

function myClearInterval(timer) {
    clearTimeout(timer.target);
}

// 手写寄生组合继承
function Parent(name){
    this.name = name;
    this.say = () => {
        console.log(11);
    }
}
Parent.prototype.play = () => {
    console.log(222);
}

function Children(name, age){
    Parent.call(this, name);
    this.age = age;
}

Children.prototype = Object.create(Parent.prototype);
Children.prototype.constructor = Children;



// 手写解析url
/**
 * --- 题目描述 ---
 * 
 * 实现一个函数，可以对 url 中的 query 部分做拆解，返回一个 key: value 形式的 object  
 * 
 * --- 实例 ---
 * 
 * 输入：'http://sample.com/?a=1&e&b=2&c=xx&d#hash' 
 * 输出：{a: 1, b: 2, c: 'xx', d: ''}  
 */

function getQueryObj(url) {
    let queryObj = {};
    urlObj = new URL(url);
    urlObj.search.slice(1, urlObj.search.length)
    .split('&').forEach(item => {
        let arr = item.split('=');
        queryObj[arr[0]] = arr[1] || '';
    })
    return queryObj;
}

/**
 * --- 题目描述 ---
 *
 * 实现一个 parseParem 函数，将 url 转化为指定结果
 *
 * --- 测试用例 ---
 *
 * 输入：url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'
 * 输出：
{
 user:'anonymous',
 id:[123,456],// 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
 city:'北京',// 中文需解码
 enabled: true // 未指定值的 key 与约定为 true
}
*/

const parseParam = (url) => {
    const queryObj = {};
    const arr = url.split('?')[1].split('&');
    arr.forEach(e => {
        const [key, value] = e.split('=');
        if(key in queryObj)
            Array.isArray(queryObj[key]) ? queryObj[key].push(value) : queryObj[key] = [queryObj[key]].concat(value);
        else
            queryObj[key] = value ? decodeURI(value) : true;
    })
    return queryObj;
}


// 手写AJAX请求
const xhr = new XMLHttpRequest();
xhr.open('GET', 'http://www.example.com:8080');
xhr.send(obj);
xhr.onreadystatechange = () => {
    if(xhr.readyState === 4){
        if(xhr.status >=200 && xhr.status < 300)
            console.log(xhr.responseText);
        else 
            console.log('请求失败');
    }
}

// Promise封装AJAX
const p = new Promise((resolve, reject) => {
    const xhr = new XMLHttpRequest()
    xhr.open('GET', 'http://www.example.com:8080');
    xhr.send(obj);
    xhr.onreadystatechange = () => {
        if(xhr.readyState === 4){
            if(xhr.status >= 200 && xhr.status < 300)
                resolve(xhr.responseText);
            else
                reject(xhr.status);
        }
    }
})
p.then(
    value => console.log(value)
).catch(
    err => console.err(err)
)


// LRU缓存
const LRUCache = class {
    constructor(capacity){
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key){
        let cache = this.cache;
        if(cache.has(key)){
            let temp = cache.get(key);
            cache.delete(key);
            cache.set(key, temp);
            return temp;
        }else {
            return -1;
        }
    }

    put(key, value){
        let cache = this.cache;
        if(cache.has(key)){
            cache.delete(key);
        } else if(cache.size > this.capacity) {
            cache.delete(cache.keys().next().value)
        }
        cache.set(key, value);
    }
}

// 手写apply
function myApply(context) {
    if(typeof this !== 'function')
        throw new TypeError('Error');
    let result = null;
    context = context || window;
    context.fn = this;
    if(arguments[1]){
        result = context.fn(...arguments[1]);
    }else
        result = context.fn();
    delete context.fn;
    return result;
}

// 手写call
function myCall(context) {
    if(typeof this !== 'function')
        throw new TypeError('Error');
    let result = null;
    const args = [...arguments].slice(1);
    context = context || window;
    context.fn = this;
    if(args){
        result = context.fn(...args);
    } else {
        result = context.fn();
    }
    delete context.fn;
    return result;
}

// 手写bind
function myBind(context) {
    if(typeof this !== 'function')
        throw new TypeError('类型错误');
    context = context || window;
    context.fn = this;
    const args = [...arguments].slice(1);
    return function Fn(){
        let result = context.fn.apply(this instanceof Fn ? this : context, args.concat(...arguments))
        delete context.fn;
        return result;
    }
}  

// 手写instanceof
function myInstanceof(leftValue, rightValue) {
    let rightProto = rightValue.prototype;
    leftValue = leftValue.__proto__;
    while(true){
        if(leftValue === null)
            return false;
        if(leftValue === rightProto)
            return true;
        leftValue = leftValue.__proto__;
    }
}

// 手写new操作符
function myNew() {
    var obj = {};
    var Constructor = [].shift.call(arguments);
    obj.__proto__ = Constructor.prototype;
    var ret = Constructor.apply(obj, arguments)
    return typeof ret === 'object' && ret !== null ? ret : obj; 
}

// 手写Promise.all
function myPromiseAll(promises){
    return new Promise((resolve, reject) => {
        if(!Array.isArray(promises))
            return reject(new TypeError('promises must be an array'));
        let resolvedCounter = 0;
        let promisesLen = promises.length;
        let resolvedValues = new Array(promisesLen);
        for(let promise of promises){
            Promise.resolve(promise).then(
                value => {
                    resolvedCounter++;
                    resolvedValues.push(value);
                    if(resolvedCounter === promisesLen) {
                        return resolve(resolvedValues)
                    }
                },
                reason => {
                    return reject(reason)
                }
            )
        }
    })
}

// 手写Promise


// 手写Promise.race
const myPromiseRace = (promises) => {
    return new Promise((resolve, reject) => {
        if(!Array.isArray(promises))
            return reject(new TypeError('promises must be an arguments'))
        for(let promise of promises){
            Promise.resolve(promise).then(
                value => {
                    return resolve(value);
                },
                reason => {
                    return reject(reason);
                }
            )
        }    
    })
}


// 手写map
function myMap(arr, mapCallback){
    if(!Array.isArray(arr) || arr.length === 0 || typeof mapCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0; i < arr.length; i++)
            result.push(mapCallback(arr[i],i, arr));
        return result;
    }
}

// 手写 reduce
function myReduce(arr, reduceCallback, initialValue) {
    if(!Array.isArray(arr) || !arr.length || typeof reduceCallback !== 'function')
        return [];
    else {
        let hasInitialValue = initialValue !== undefined;
        let value = hasInitialValue ? initialValue : arr[0];
        for(let i = 0; i < arr.length; i++) {
            value = reduceCallback(value,arr[i],i,arr);
        }
        return value;
    }
}

// 手写filter
function myFilter(arr, filterCallback){
    if(!Array.isArray(arr) || !arr.length || typeof filterCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0;i < arr.length; i++){
            if(filterCallback(arr[i], i, arr))
                result.push(arr[i]);
        }
        return result;
    }
}

// 找出不含有重复字符的最长子串长度
var lengthOfLongestSubstring = (s) => {
    let window = {};
    let left = 0 ,right = 0;
    let maxLen = 0;

    while(right < s.length) {
        let current = s[right];
        window[current] ? window[current]++ : window[current] = 1;
        right++;
        while(window[current] > 1){
            let now = s[left];
            left++;
            window[now]--;
        }
        maxLen = Math.max(maxLen, right - left)
    }
    return maxLen;
}

// 数组去重
console.log(new Set(arr));
console.log(arr.filter(((item,index) =>
    arr.indexOf(item) === index
)))
console.log(arr.reduce((prev,cur) => 
    prev.includes(cur) ? prev : [...prev,cur]
, []))


function noRepeat(arr){
    for(let i = 0;i < arr.length; i++){
        if(arr.indexOf(arr[i]) !== i){
            arr.splice(i, 1);
            i--;
        }
    }
    return arr;
}



// 数组扁平化
const flat = (arr) => {
    const result = [];
    arr.forEach(item =>{
        if(Array.isArray(item))
            result = result.concat(flat(item));
        else
            result.push(item);
    })
    return result;
}

const flat2 = (arr) => {
    return arr.reduce((prev,cur)=> {
        if(Array.isArray(cur))
            return prev.concat(flat(cur));
        else
            return prev.concat(cur);
    },[]);
}

// 用栈的思路
const flat3 = (arr) => {
    const stack = arr.slice();
    const result = [];

    while(stack.length){
        let temp = stack.pop();
        if(Array.isArray(temp))
            stack.push(...temp);
        else 
            result.unshift(temp);
    }
    return result;
}
